package club.vann.nowcoder;

import club.vann.nowcoder.common.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * <p>难度：Medium</p>
 * <p>题目：实现二叉树先序/中序/后序遍历</p>
 * <p>描述：分别按照二叉树先序，中序和后序打印所有的节点。
 * 示例1
 * 输入
 * 复制
 * {1,2,3}
 * 返回值
 * 复制
 * [[1,2,3],[2,1,3],[2,3,1]]
 * 备注:
 * n \leq 10^6n≤10
 * 6</p>
 * @author vann
 * @program now-coder
 * @description
 * @date 2021-03-13:15:46:38
 */
public class NC45 {
    public static void main(String[] args) {

    }

    /**
     *
     * @param root TreeNode类 the root of binary tree
     * @return int整型二维数组
     */
    public int[][] threeOrders (TreeNode root) {
        int[][] ans = new int[3][];
        List<Integer> preList = new ArrayList<>();
        preOrders(preList, root);
        int[] preArray = new int[preList.size()];
        int i = 0;
        for(int x : preList) {
            preArray[i++] = x;
        }
        ans[0] = preArray;

        List<Integer> inList = new ArrayList<>();
        inOrders(inList,root);
        int[] inArray = new int[inList.size()];
        int j = 0;
        for(int x : inList) {
            inArray[j++] = x;
        }
        ans[1] = inArray;

        List<Integer> backList = new ArrayList<>();
        backOrder(backList, root);
        int[] backArray = new int[backList.size()];
        int t = 0;
        for(int x : backList) {
            backArray[t++] = x;
        }
        ans[2] = backArray;
        return ans;
    }

    private void preOrders(List<Integer> list, TreeNode node) {
        if(node == null) {
            return;
        }

        list.add(node.val);
        preOrders(list, node.left);
        preOrders(list, node.right);
    }

    private void inOrders(List<Integer> list, TreeNode node) {
        if(node == null) {
            return;
        }
        inOrders(list, node.left);
        list.add(node.val);
        inOrders(list, node.right);
    }

    private void backOrder(List<Integer> list, TreeNode node) {
        if(node == null) {
            return;
        }

        backOrder(list, node.left);
        backOrder(list, node.right);
        list.add(node.val);
    }
}
